§ 1.1 Field of the Invention
The present invention concerns methods, apparatus and data structures for providing a transport network employing technologies that are independent of technologies used to access it, that supports various applications, and that supports the provision of various service levels. The present invention also concerns facilitating simple peering over such a transport network. More specifically, the present invention concerns maintaining routing information.
§ 1.2 Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention. Basic communications terminology is introduced in § 1.2.1 below for the reader's convenience. Then, known transport network technologies are introduced in § 1.2.2 below. Thereafter, limitations of such known transport network technologies are introduced in § 1.2.3 below. Finally, various goals of the present invention are introduced in § 1.2.4 below.
§ 1.2.1 Basic Communications Terminology
Although networking software and network reference models are known to those skilled in the art, they are introduced in §§ 1.2.1.1 and 1.2.1.2 below for the reader's convenience.
§ 1.2.1.1 Communications Protocol Stack
To reduce their complexity, networks may be organized as a series of layers, each one built upon the one below it as shown in FIG. 1. Each layer functions to offer certain services to the higher layer, thereby shielding those higher layers from the details of how the offered services are actually implemented. The entities comprising the corresponding layers on different machines are called “peers”. Such peers use rules and conventions, also referred to as the layer n protocol, to communicate with each other as depicted by the dashed lines in FIG. 1. Actually, no data are directly transferred from layer n on one machine to layer n on another machine. Rather, in the machine transmitting the data, each layer passes data and control information to the layer immediately below it, until the lowest layer (layer 1) is reached. Below layer 1, is a physical medium 110 through which actual communications take place. At the machine receiving the data, each layer passes data and control information to the layer immediately above it until the highest layer is reached. Thus, referring to FIG. 1, actual communications take place via the solid lines and the physical medium 110, while virtual peer-to-peer communications occur via the dashed lines.
Still referring to FIG. 1, interfaces are arranged between adjacent layers. Each of these interfaces defines primitive operations and services that the lower layer offers to the upper layer.
The set of layers and protocols may be referred to as a “network architecture”. A list of protocols used by a system, one protocol per layer, may be referred to as a “protocol stack” or “protocol suite”.
§ 1.2.1.2 Network Architecture Reference Models
FIG. 2 illustrates a comparison of the Open Systems Interconnection (or “OSI”) reference model 210 for network architectures and the transfer control protocol/Internet protocol (or “TCP/IP”) reference model 220 for network architectures. Although those skilled in the art will be familiar with both reference models, each is introduced below for the reader's convenience.
§ 1.2.1.2.1 The OSI Reference Model
As shown in FIG. 2, the OSI reference model 210 has seven (7) distinct layers; namely, (i) a physical layer 211, (ii) a data link layer 212, (iii) a network layer 213, (iv) a transport layer 214, (v) a session layer 215, (vi) a presentation layer 216, and (vii) an application layer 217. Each layer is briefly introduced below.
The physical layer 211 deals with transmitting raw bits over a communications channel. Thus, the physical layer is typically concerned with mechanical, electrical, optical, and procedural interfaces, as well as the physical transmission medium (e.g., twisted copper pair, co-axial cable, optical fiber, etc.) that lies below the physical layer.
The data link layer 212 functions to transform a raw communications facility into a line that appears free from undetected transmission errors to the network layer 213. The data link layer 212 does this by having the sending host segment its data into “data frames”, transmitting these frames to the receiving host, and processing “acknowledgement frames” sent back from the receiver.
The network layer 213 functions to control the operation of a subnetwork between the hosts and controls the routing of packets between the hosts.
The transport layer 214 functions to accept data from the session layer 215 and segment this data into smaller units, if necessary, for use by the network layer 213. The transport layer 214 also determines a type of service (e.g., error-free, point-to-point) to provide to the session layer 215. Further, the transport layer 214 controls the flow of data between hosts. The transport layer 214 is a true “end-to-end” layer, from source host to destination host, since a program on the source machine converses with a similar program on the destination machine, using message headers and control messages.
The session layer 215 functions to allow different machines to establish sessions between them. The session layer 215 may manage dialog control and maintain synchronization.
The presentation layer 215 concerns the syntax and semantics of information transmitted.
The application layer 216 may function to define network virtual terminals that editors and other programs can use, and to transfer files.
§ 1.2.1.2.2 The TCP/IP Model
In recent decades, and in the past five (5) to ten (10) years in particular, computers have become interconnected by networks by an ever increasing extent; initially, via local area networks (or “LANs”), and more recently via LANs, wide area networks (or WANs) and the Internet. In 1969, the Advanced Research Projects Agency (ARPA) of the U.S. Department of Defense (DoD) deployed ARPANET as a way to explore packet-switching technology and protocols that could be used for cooperative, distributed, computing. Early on, ARPANET was used by the TELNET application that permitted a single terminal to work with different types of computers, and by the file transfer protocol (or “FTP”) which permitted different types of computers to transfer files from one another. In the early 1970s', electronic mail became the most popular application which used ARPANET.
This packet switching technology was so successful, that the ARPA applied it to tactical radio communications (Packet Radio) and to satellite communications (SATNET). However, since these networks operated in very different communications environments, certain parameters, such as maximum packet size for example, were different in each case. Thus, methods and protocols were developed for “internetworking” these different packet switched networks. This work lead to the transmission control protocol (or “TCP”) and the internet protocol (or “IP”) which became the TCP/IP protocol suite. Although the TCP/IP protocol suite, which is the foundation of the Internet, is known to those skilled in the art, it is briefly described below for the reader's convenience.
As shown in FIG. 2, the TCP/IP reference model 220 includes a physical layer 221, a network access layer 222, an internet layer 223, a transport layer 224, and an application layer 225. Each of these layers is briefly introduced below.
The physical layer 221 defines the interface between a data transmission device (e.g., a computer) and a transmission medium (e.g., twisted pair copper wires, co-axial cable, optical fiber, etc.). It specifies the characteristics of the transmission medium, the nature of the signals, the data rate, etc.
The network access layer 222 defines the interface between an end system and the network to which it is attached. It concerns access to, and routing data across, a network. Frame relay is an example of a network access layer.
The internet layer 223 functions to permit hosts to inject packets into any network and have them travel independently to the destination machine (which may be on a different network). Since these packets may travel independently, they may arrive in an order other than the order in which they were sent. Higher layers can be used to reorder the packets. Thus, the main function of the internet layer 320 is to deliver (e.g., route) IP packets to their destination.
The transport layer 224 is an end-to-end protocol. For example, the transmission control protocol (or “TCP”) is a reliable connection-oriented protocol that allows a byte stream originating on one machine to be delivered, without error, on any other machine on the Internet. More specifically, the TCP protocol fragments an incoming data stream into discrete messages, each of which is passed to the internet layer 223. At the destination, the TCP protocol reassembles the received messages into an output stream.
The TCP/IP model 220 does not have session and presentation layers. Instead, an application layer 225 contains all of the higher-level protocols that are used to support various types of end use applications (e.g., the simple mail transfer protocol (or “SMTP”) for e-mail, the file transfer protocol (or “FTP”), etc.).
The TCP/IP model does not define what occurs below the internet layer 223, other than to note that the host has to connect to the network using some protocol so that it can send IP packets over it. This protocol varies from host to host and network to network.
Basically, each of the layers encapsulates, or converts, data in a higher layer. For example, referring to FIG. 4, user data 400 as a byte stream is provided with a TCP header 402 to form a TCP segment 410. The TCP segment 410 is provided with an IP header 412 to form an IP datagram 420. The IP datagram 420 is provided with a network header 422 to define a network-level packet 430. The network-level packet 430 is then converted to radio, electrical, optical (or other) signals sent over the transmission medium at a specified rate with a specified type of modulation.
The TCP header 402, as illustrated in FIG. 5, includes at least twenty (20) octets (i.e., 160 bits). Fields 502 and 504 identify ports at the source and destination systems, respectively, that are using the connection. Values in the sequence number 506, acknowledgement number 508 and window 516 files are used to provide flow and error control. The value in the checksum field 518 is used to detect errors in the TCP segment 410.
FIGS. 6A and 6B illustrate two (2) alternative IP headers 412 and 412′, respectively. Basically, FIG. 6A depicts the IP protocol (Version 4) that has been used. FIG. 6B depicts a next generation IP protocol (Version 6) that, among other things, provides for more source and destination addresses.
More specifically, referring to FIG. 6A, the four (4) bit version field 602 indicates the version number of the IP, in this case, version 4. The 4-bit Internet header length field 604 identifies the length of the header 412 in 32-bit words. The 8-bit type of service field 606 indicates the service level that the IP datagram 420 should be given. The 16-bit total length field 608 identifies the total length of the IP datagram 420 in octets. The 16-bit identification field 610 is used to help reassemble fragmented user data carried in multiple packets. The 3-bit flags field 612 is used to control fragmentation. The 13-bit fragment offset field 614 is used to reassemble a datagram 420 that has become fragmented. The 8-bit time to live field 616 defines a maximum time that the datagram is allowed to exist within the network it travels over. The 8-bit protocol field 618 defines the higher-level protocol to which the data portion of the datagram 420 belongs. The 16-bit header checksum field 620 permits the integrity of the IP header 412 to be checked. The 32-bit source address field 322 contains the IP address of the sender of the IP datagram 420 and the 32-bit destination address field contains the IP address of the host to which the IP datagram 120 is being sent. FIG. 3 illustrates IP address formats. Options and padding 626 may be used to describe special packet processing and/or to ensure that the header 412 is a complete multiple of 32-bit words.
Referring to FIG. 6B, the four (4) bit version field 602 indicates the version number of the IP, in this case, version 6. The 4-bit priority field 628 enables a sender to prioritize packets sent by it. The 24-bit flow label field 630 is used by a source to label packets for which special handling is requested. The 16-bit payload length field 632 identifies the size of data carried in the packet. The 8-bit next header field 634 is used to indicate whether another header is present and if so, to identify it. The 8-bit hop limit field 636 serves to discard the IP datagram 420 if a hop limit (e.g., the number of times the packet is routed) is exceeded. Also provided are 128-bit source and destination address fields 322′ and 324′, respectively.
Having described the TCP/IP protocol stack 220, the routing of a TCP/IP packet is now described.
A TCP/IP packet is communicated over the Internet (or any internet or intranet) via routers. Basically, routers in the Internet use destination address information (Recall fields 624 and 624′.) to forward packets towards their destination. Routers interconnect different networks. More specifically, routers accept incoming packets from various connected networks, use a look-up table to determine a network upon which the packet should be placed, and routes the packet to the determined network.
FIG. 7, which includes FIGS. 7A through 7C, illustrates the communication of data from a sender, to a receiver, using the TCP/IP protocol stack. Referring first to FIG. 7A, an application protocol 702 prepares a block of data (e.g., an e-mail message (SMTP), a file (FTP), user input (TELNET), etc.) 400 for transmission. Before the data 400 are sent, the sending and receiving applications agree on a format and encoding and agree to exchange data (Recall, e.g., the peer-to-peer communications depicted with dashed lines in FIG. 1.). If necessary, the data are converted (character code, compression, encryption, etc.) to a form expected by the destination device.
The TCP layer 704 may segment the data block 400, keeping track of the sequence of segments. Each TCP segment 410 includes a header 402 containing a sequence number (recall field 506) and a frame check sequence to detect errors. A copy of each TCP segment is made so that if a segment is lost or damaged, it can be retransmitted. When an acknowledgement of safe receipt is received from the receiver, the copy of the segment is erased.
The IP layer 706 may break the TCP segment into a number of datagrams 420 to meet size requirements of networks over which the data will be communicated. Each datagram includes the IP header 412.
A network layer 708, such as frame relay for example, may apply a header and trailer 422 to frame the datagram 420. The header may include a connection identifier and the trailer may contain a frame check sequence for example. Each frame 430 is then transmitted, by the physical layer 710, over the transmission medium as a sequence of bits.
FIG. 7B illustrates the operation of the TCP/IP protocol stack at a router in the network. The physical layer 712 receives the incoming signal 430 from the transmission medium and interprets it as a frame of bits. The network (e.g., frame relay) layer 714 then removes the header and trailer 422 and processes them. A frame check sequence may be used for error detection. A connection number may be used to identify the source. The network layer 714 then passes the IP datagram 420 to the IP layer 718.
The IP layer examines the IP header 412 and makes a routing decision (Recall the destination address 324, 324′). A local line control (or “LLC”) layer 720 uses a simple network management protocol (or “SNMP”) and adds a header 750 that contains a sequence number and address information. Another network layer 722 (e.g., media access control (or “MAC”)) adds a header and trailer 760. The header may contain address information and the trailer may contain a frame check sequence. The physical layer 724 then transmits the frame 450 over another transmission medium.
FIG. 7C illustrates the operation of the TCP/IP protocol stack at a receiver. The physical layer 732 receives the signals from the transmission medium and interprets them as a frame of bits. The network layer 734 removes the header and trailer 760 and processes them. For example, the frame check sequence in the trailer may be used for error detection. The resulting packet 440 is passed to the transport layer 736, which processes the header 750 for flow and error control. The resulting IP datagram 420 is passed to the IP layer 738, which removes the header 412. Frame check sequence and other control information may be processed at this point.
The TCP segment 410 is then passed to the TCP layer 740, which removes the header 402 and may check the frame check sequence. (In the event of a match, the match is acknowledged and in the event of a mismatch, the packet is discarded.) The TCP layer 740 then passes the data 400 to the application layer 742. If the user data was segmented (or fragmented), the TCP layer 740 reassembles it. Finally, the application layer 742 performs any necessary transformations, such as decompression and decryption for example, and directs the data to an appropriate area of the receiver, for use by the receiving application.
§ 1.2.2 Known Transport Network Technologies
For many entities (such as businesses, universities, etc.), local area networks (or “LANs”) suffice for intra-entity communications. Indeed, LANs are quite popular since they are relatively inexpensive to deploy, operate, and manage, and are based on mature, well-developed technology (e.g., Ethernet). The LANs' (by definition) compact geographic scope limits wiring expenses. The use of mature technologies and the fact that most LANs support limited numbers of hosts simplifies operations and management. Unfortunately, however, most entities need to communicate (voice and/or data) with their own facilities, or others, beyond their immediate location. Thus, wide area networks (or “WANs”) are needed. Very often, entities want at least some privacy or security attached to their communications.
Presently, private long-haul communications can take place over networks that can be generally classified into two types—dedicated WANs that facilitate communications among multiple sites, and public transport networks that allow one or more sites of a private network to communicate. Both of these types of networks is introduced below.
Dedicated wide area networks (WANs) are typically implemented using leased lines or dedicated circuits to connect multiple sites. Customer premise equipment (or “CPE”) routers or switches at theses sites connect these leased lines or dedicated circuits together to facilitate connectivity between each site of the network. Most private networks with a relatively large number of sites will not have “fully meshed” networks (i.e., direct connections between each of the sites) due to the cost of leased lines or dedicated circuits and to the complexity of configuring and managing customer premises equipment. Rather, some form of hierarchical network topology is typically employed in such instances.
Public transport networks, which are typically deployed by regional bell operating companies (or “RBOCs”), are often used to allow remote users to connect to an enterprise network using the public-switched telephone network (or “PSTN”), an integrated services digital network (or “ISDN”), or some other type of transport network technology. (Note that the word “public” in the phrase “public transport network” connotes the fact that more than one entity may use it, even though it may be privately owned and managed, and not available to the general public.) Such remote access may be facilitated by deploying network access servers (or NASs) at one or more central cites. When users connect to (e.g., dial into) a NAS, it works with authentication, authorization and accounting (or “AAA”) servers to verify the identity of the user and to check which services that user is authorized to use.
Unfortunately, both dedicated WANs and existing transport networks have a number of limitations, at least some of which are introduced in § 1.2.3 below.
§ 1.2.3 Limitations of Known Transport Networks
As can be appreciated, private dedicated WANs are beyond the financial reach of most entities. Accordingly, so-called public transport networks have become quite popular. Unfortunately, however, various kinds of incompatible public transport networks have been introduced over the years in response to the then perceived needs to support various applications. Examples of such public transport network technologies include switched multimegabit data service (or “SMDS”), X.25 packet switched networks, frame relay, broadband ISDN, and asynchronous transport mode (or “ATM”).
Briefly stated, SMDS was designed to connect together multiple LANs, typically those at the branch offices and factories of a given company. SMDS is switched, is not connection-oriented, has a normal speed of 45 Mbps, supports a maximum payload of 9188 bytes, and supports multicasting but not permanent virtual circuits. X.25 was designed to provide an interface between public packet-switched networks and their customers. X.25 is connection-oriented, is switched, has a normal speed of 64 Kbps, supports a maximum payload of 128 bytes, and supports permanent virtual channels, but not multicasting. Frame relay was designed to provide an absolute bare-bones connection-oriented way to move bits at reasonable speed and low cost. Frame relay is connection-oriented, is not switched, has a normal speed of 1.5 Mbps, supports a maximum payload of 1600 bytes, and supports permanent virtual circuits, but not multicasting. Finally, ATM is connection-oriented, is switched, has a normal speed of 155 Mbps, has a variable payload, and supports both permanent virtual circuits and multicasting.
It is important to reiterate that these public transport networks are incompatible. This fact has two onerous implications for communications companies. First, technologies with which customers access the transport network (referred to as “access technologies”) must be compatible with the technology used in the transport network (unless there is a handoff between networks, which is expensive). Thus, customers are locked into a technology from end-to-end. Further, as illustrated in FIG. 8, such dependencies between access technologies and transport network technologies have forced public transport network owners, typically RBOCs, to support, maintain and administer (See administrations 820.) separate networks 810.
Second, various applications and potential applications of communications networks, such as voice, video-on-demand, audio-on-demand, e-mail, voice-mail, video conferencing, multicasting, broadcasting, Internet access, billing, authorization, authentication, and accounting, caching, fire-walling, etc., have different network requirements, such as requirements related to maximum permissible latency, data loss, delay jitter, bandwidth, network security, etc. Consequently, customers are expected to demand various levels of service offered at various prices. Unfortunately, some of the above-referenced public transport network technologies cannot support all of the aforementioned applications. For example, they may not offer adequate bandwidth, security, and/or adequate quality of service measures to support the aforementioned applications. Even if the various public transport network technologies did provide such quality of service support, supporting various service levels and types, globally, across a number of different transport networks greatly exacerbates the problem of supporting multiple networks. Indeed, the inventors believe that such global quality of service across a number of different networks hasn't even been attempted.
It is important to note that regarding the TCP/IP protocol, introduced in § 1.2.1.2.2 above, a number of packet forwarding and routing protocols, ostensibly supporting the provision of various service levels, have been proposed. Such protocols include multi-protocol label switching (or “MPLS”), resource reservation protocol (or “RSVP”), and differentiated services (or “DiffServ”). Unfortunately, presently, very few people have expertise with these protocols. Indeed, many are still evolving and are largely undefined. Further, it is unclear whether or not these protocols will scale well in networks supporting a large number of customers, particularly if they are “stateful” (i.e., require the state of the network, where the state is coherent across all or many nodes of the network). It is also unclear how these protocols will deal with issues of separately owned and operated networks (i.e., autonomous systems).
Thus, a better public transport network is needed.
§ 1.2.4 Goals
It is an object of the present invention to support various applications, such as video-on-demand, audio-on-demand, voice communications, data communications, e-mail, voice-mail, video conferencing, multicasting, broadcasting, Internet access, billing, virtual private networks, caching, fire-walling, etc. Since these various applications have different network requirements, it is a further goal of the present invention to provide a mechanism that may be used to support various levels and types of service.
It is a further object of the invention to provide a public transport network employing technologies that are independent of the technologies used to access it. In this way, the transport network can use a single technology to support various different access technologies and services. Such independence would allow communications companies, such as RBOCs for example, to use any transport network technology they chose. Further, in this way, network management is simplified since only a single technology is needed to support the public transport network. Advantageously, this also simplifies the process of providing various service levels and service types, by the communications companies.
The technology used in the public transport network should be proven, robust, and scalable.
It is yet another object of the present invention to permit customers to dynamically update customer addressing (e.g., routing) information, using any standard (e.g., routing) protocol, in a secure and transparent manner. Such updates should not require the customer to have extensive network expertise, such as knowledge of exterior gateway protocols like BGP-4. Thus, it is an object of the invention to permit a customer to simply plug in a device and start using it (within a short time) to communicate with other of their devices via the transport network.
Assuming that a communications company, such as an RBOC for example, chooses to base its public transport network on the internet protocol (or “IP”), a number of advantages are had. More specifically, there are a great number of commodity products support IP, there is a large labor base with knowledge of IP, and there are a large number of IP tools available. Further, quality of service and virtual private routed networks over IP are supported. However, using IP in a public transport network introduces a number of challenges.
First, many IP commodity products, such as routers for example, have large bandwidth capacity, but limited numbers of physical ports. Therefore aggregation is needed. Such aggregation may be achieved in two ways. First, virtual channels can be used to preserve addressing. Alternatively, customers can be uniquely identified in some way so that trunking may be used.
Presently, digital subscriber line access multiplexers (or “DSLAMs”) may be used to concentrate traffic in asynchronous digital subscriber line (or “ADSL”) implementations by using time division multiplexing. Basically, a DSLAM can accept twisted copper pairs supporting ADSL service and provide them on virtual channels on a shared common communications medium, such as an OC3 (e.g., 155.52 Mbps) fiber channel. However, an asynchronous transfer mode (or “ATM”) switch is needed to switch these physical connections to virtual channels, thereby necessitating an ATM switch port for each customer connection. Aside from physically requiring a lot of space, using a DSLAM for this purpose is expensive on a per port basis.
Thus, improved techniques are needed to aggregate physical connections, for example, for presentation to an access router at the edge of a public transport network. In this regard, it is an object of the present invention to aggregate a large number of physical connections, for presentation to a small number of high bandwidth ports.
Second, in the context of virtual private networks, a layer 3 (e.g., IP) address is not necessarily globally unique. Thus, it is a further object of the present invention to enable proper end-to-end data (e.g., packet) forwarding, even in instances where it cannot be assumed that layer 3 addresses are globally unique.
Finally, it is an object of the present invention to provide a transport network in which customer data is private and secure.